{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Window Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minWindow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小覆盖子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 、一个字符串 <code>t</code> 。返回 <code>s</code> 中涵盖 <code>t</code> 所有字符的最小子串。如果 <code>s</code> 中不存在涵盖 <code>t</code> 所有字符的子串，则返回空字符串 <code>\"\"</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于 <code>t</code> 中重复字符，我们寻找的子字符串中该字符数量必须不少于 <code>t</code> 中该字符数量。</li>\n",
    "\t<li>如果 <code>s</code> 中存在这样的子串，我们保证它是唯一的答案。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ADOBECODEBANC\", t = \"ABC\"\n",
    "<strong>输出：</strong>\"BANC\"\n",
    "<strong>解释：</strong>最小覆盖子串 \"BANC\" 包含来自字符串 t 的 'A'、'B' 和 'C'。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"a\", t = \"a\"\n",
    "<strong>输出：</strong>\"a\"\n",
    "<strong>解释：</strong>整个字符串 s 是最小覆盖子串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"a\", t = \"aa\"\n",
    "<strong>输出:</strong> \"\"\n",
    "<strong>解释:</strong> t 中两个字符 'a' 均应包含在 s 的子串中，\n",
    "因此没有符合条件的子字符串，返回空字符串。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code><sup>m == s.length</sup></code></li>\n",
    "\t<li><code><sup>n == t.length</sup></code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>进阶：</strong>你能设计一个在 <code>o(m+n)</code> 时间内解决此问题的算法吗？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-window-substring](https://leetcode.cn/problems/minimum-window-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-window-substring](https://leetcode.cn/problems/minimum-window-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ADOBECODEBANC\"\\n\"ABC\"', '\"a\"\\n\"a\"', '\"a\"\\n\"aa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        i, j, n = 0, 0, len(s)\n",
    "        overflow = defaultdict(int)\n",
    "        underflow = defaultdict(int)\n",
    "        chars = {}\n",
    "        ret = (-1, n)\n",
    "        for c in t:\n",
    "            underflow[c] += 1\n",
    "            chars[c] = 1\n",
    "        c = s[0]\n",
    "        add = True\n",
    "        while i <= n-1 and j <= n-1:\n",
    "            if c in chars:\n",
    "                if add:\n",
    "                    if c in underflow:\n",
    "                        underflow[c] -= 1\n",
    "                        if underflow[c] == 0:\n",
    "                            underflow.pop(c)\n",
    "                    else:\n",
    "                        overflow[c] += 1\n",
    "                else:\n",
    "                    if overflow[c] == 0:\n",
    "                        underflow[c] += 1\n",
    "                    else:\n",
    "                        overflow[c] -= 1\n",
    "            if underflow.keys():\n",
    "                j += 1\n",
    "                if j<=n-1: c = s[j]\n",
    "                add = True\n",
    "            else:\n",
    "                if j - i < ret[1] - ret[0]:\n",
    "                    ret = (i, j)\n",
    "                c = s[i]\n",
    "                i += 1\n",
    "                add = False\n",
    "        if ret[0] == -1:\n",
    "            return ''\n",
    "        else:\n",
    "            return s[ret[0]:ret[1]+1]\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minWindow(self, s, t):\n",
    "        c = [0] * 128\n",
    "        counter = 0\n",
    "        for tt in t:\n",
    "            c[ord(tt)] += 1\n",
    "            counter += 1\n",
    "        l, r = 0, 0\n",
    "        ret, shortest = '', len(s) + 1\n",
    "        for r in range(len(s)):\n",
    "            if c[ord(s[r])] > 0:\n",
    "                counter -= 1\n",
    "            c[ord(s[r])] -= 1\n",
    "            while counter == 0:\n",
    "                if r - l + 1 < shortest:\n",
    "                    shortest = r - l + 1\n",
    "                    ret = s[l:r+1]\n",
    "                if c[ord(s[l])] == 0:\n",
    "                    counter += 1\n",
    "                c[ord(s[l])] += 1\n",
    "                l += 1\n",
    "        return ret\n",
    "    \n",
    "    # my original thought\n",
    "    def minWindow2(self, s: 'str', t: 'str') -> 'str':\n",
    "        ns, nt = len(s), len(t)\n",
    "        if ns < nt:\n",
    "            return \"\"\n",
    "        count_s, count_t = Counter(), Counter(t)\n",
    "        l, r = 0, 0\n",
    "        matched = False\n",
    "        to_match = sum(count_t.values())\n",
    "        ret, shortest = \"\", ns + 1\n",
    "        for r in range(ns):\n",
    "            if matched:\n",
    "                if s[r] in count_t.keys():\n",
    "                    if s[l] == s[r]:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        count_s[s[r]] += 1\n",
    "                    while s[l] not in count_t.keys() or count_s[s[l]] > count_t[s[l]]:\n",
    "                        if count_s[s[l]] > count_t[s[l]]:\n",
    "                            count_s[s[l]] -= 1\n",
    "                        l += 1\n",
    "                    if r - l + 1 < shortest:\n",
    "                        shortest = r - l + 1\n",
    "                        ret = s[l:r + 1]\n",
    "            else:\n",
    "                if s[r] in count_t.keys():\n",
    "                    if count_s[s[r]] < count_t[s[r]]:\n",
    "                        to_match -= 1\n",
    "                    if to_match == 0:\n",
    "                        matched = True\n",
    "                        while s[l] not in count_t.keys() or count_s[s[l]] > count_t[s[l]]:\n",
    "                            if count_s[s[l]] > count_t[s[l]]:\n",
    "                                count_s[s[l]] -= 1\n",
    "                            l += 1\n",
    "                        shortest = r - l + 1\n",
    "                        ret = s[l:r + 1]\n",
    "                    count_s[s[r]] += 1\n",
    "            # print(ret, s[l:r+1], count_s, count_t)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections \n",
    "class Solution:\n",
    "    # def minWindow(self, s, t):\n",
    "    #     \"\"\"\n",
    "    #     :type s: str\n",
    "    #     :type t: str\n",
    "    #     :rtype: str\n",
    "    #     \"\"\"\n",
    "        # Solution 1: 先找到最小窗口的最右端的位置，再找到左端移动位置后即发生不满足要求的前一个位置，反馈对应两个位置截取的字符串。字典记录T字符串中字符的增减情况,记录符合条件的最短字符串的值。\n",
    "#         res = ''\n",
    "#         t_size = len(t)\n",
    "#         mapping = {}\n",
    "#         left, cnt, minlen = 0, 0, float('inf')\n",
    "#         for i in t:\n",
    "#             mapping[i] = mapping.get(i, 0) + 1\n",
    "#         # 初始化mapping存储字符串T出现的字母次数\n",
    "        \n",
    "#         for j in range(len(s)):\n",
    "#             mapping[s[j]] = mapping.get(s[j], 0) - 1\n",
    "#             if mapping.get(s[j]) >= 0:\n",
    "#                 cnt += 1\n",
    "#             while cnt == t_size:\n",
    "#                 if minlen > j - left + 1:\n",
    "#                     minlen = j - left + 1\n",
    "#                     res = s[left:minlen]\n",
    "#                 mapping[s[left]] = mapping.get(s[left]) + 1\n",
    "#                 if mapping[s[left]] > 0:\n",
    "#                     cnt -= 1\n",
    "#                 left += 1\n",
    "#         return res\n",
    "    \n",
    "#     def minWindow(self, s, t):\n",
    "#         res = ''\n",
    "#         left, cnt, minlen = 0, 0, float('inf')\n",
    "#         mapping = collections.Counter(t)\n",
    "#         # 初始化mapping存储字符串T出现的字母次数\n",
    "        \n",
    "#         for j in range(len(s)):\n",
    "#             mapping[s[j]] -= 1\n",
    "#             if mapping[s[j]] >= 0:\n",
    "#                 cnt += 1\n",
    "#             while cnt == len(t):\n",
    "#                 if minlen > j - left + 1:\n",
    "#                     minlen = j - left + 1\n",
    "#                     res = s[left:j + 1]\n",
    "#                 mapping[s[left]] += 1\n",
    "#                 if mapping[s[left]] > 0:\n",
    "#                     cnt -= 1\n",
    "#                 left += 1\n",
    "#         return res\n",
    "    \n",
    "    # Solution 2: 由字典改为128长度的int列表进行判断，通过记录比对对应位置字符出现的次数进行最短字符串判断\n",
    "    def minWindow(self, s, t):\n",
    "        res = ''\n",
    "        left, cnt, minlen = 0, 0, float('inf')\n",
    "        mapping = [0 for x in range(128)]\n",
    "        for i in t:\n",
    "            mapping[ord(i)] += 1\n",
    "        # 初始化mapping存储字符串T出现的字母次数\n",
    "        \n",
    "        for j in range(len(s)):\n",
    "            mapping[ord(s[j])] -= 1\n",
    "            if mapping[ord(s[j])] >= 0:\n",
    "                cnt += 1\n",
    "            while cnt == len(t):\n",
    "                if minlen > j - left + 1:\n",
    "                    minlen = j - left + 1\n",
    "                    res = s[left:j + 1]\n",
    "                mapping[ord(s[left])] += 1\n",
    "                if mapping[ord(s[left])] > 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        left, right, count, tcounnt = 0, 0, 0, 0\n",
    "        res, queue = \"\", []\n",
    "        tdict, valid = {}, {}\n",
    "        for item in t:\n",
    "            count += 1\n",
    "            tdict[item] = 0\n",
    "            valid[item] = valid[item]+1 if item in valid else 1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in t:\n",
    "                left, right = i, i\n",
    "                break\n",
    "        # print(right)\n",
    "        while right < len(s):\n",
    "            # 如果不有效right++\n",
    "            if s[right] in t:\n",
    "                tdict[s[right]] += 1\n",
    "                queue.append(right)\n",
    "                if tdict[s[right]] <= valid[s[right]]:\n",
    "                    tcounnt += 1\n",
    "            if count == tcounnt:\n",
    "                if not res:\n",
    "                    res = s[left:right+1]\n",
    "                else:\n",
    "                    if right - left + 1 < len(res):\n",
    "                        res = s[left:right+1]\n",
    "                del queue[0]\n",
    "                tdict[s[left]] -= 1\n",
    "                if tdict[s[left]] < valid[s[left]]:\n",
    "                    tcounnt -= 1\n",
    "                if not queue:\n",
    "                    right += 1\n",
    "                    left = right\n",
    "                    continue\n",
    "                else:\n",
    "                    left = queue[0]\n",
    "                while tcounnt == count and queue:\n",
    "                    if right - left + 1 < len(res):\n",
    "                        res = s[left:right+1]\n",
    "                    del queue[0]\n",
    "                    tdict[s[left]] -= 1\n",
    "                    if tdict[s[left]] < valid[s[left]]:\n",
    "                        tcounnt -= 1\n",
    "                    if not queue:\n",
    "                        right += 1\n",
    "                        left = right\n",
    "                        continue\n",
    "                    else:\n",
    "                        left = queue[0]\n",
    "\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dict1 = {} #用来存放t中字符出现的次数\n",
    "        for i in t:\n",
    "            if i in dict1:\n",
    "                dict1[i] += 1\n",
    "            else:\n",
    "                dict1[i] = 1\n",
    "        count = len(t)  #计数用，计算t中字符是否全部用完\n",
    "        start = 0       #存放结果开头\n",
    "        d = len(s) + 1  #最小长度的结果字符串\n",
    "        head = 0        #最小长度的开头\n",
    "        end = 0\n",
    "        left, right = 0,len(s)\n",
    "        while end < len(s):\n",
    "            if s[end] in dict1:\n",
    "                if dict1[s[end]] > 0:\n",
    "                    count -= 1\n",
    "                dict1[s[end]] -= 1                    \n",
    "            while count == 0:\n",
    "                if end - start + 1 < d:\n",
    "                    d= end - start + 1 \n",
    "                    head = start\n",
    "                    print(head,d)\n",
    "                if s[start] in dict1:\n",
    "                    dict1[s[start]] += 1\n",
    "                    if dict1[s[start]] > 0:\n",
    "                        count += 1\n",
    "                start += 1\n",
    "            end += 1\n",
    "        if d == len(s) + 1:\n",
    "            return ''\n",
    "        else:\n",
    "            print(head,head+d)\n",
    "            print(s[0])\n",
    "            return s[head:head+d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        need, missing = collections.Counter(t), len(t)#counter是计数字典 前面是字母 后面是对应字母出现的次数  次数由大到小一般\n",
    "        i = I = J = 0 #初始化变量\n",
    "        for j, c in enumerate(s, 1):#enumerate(sequence, [start=0]) 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列\n",
    "            missing -= need[c] > 0  #j应该是序号  而c是字母\n",
    "            need[c] -= 1\n",
    "            if not missing:\n",
    "                while need[s[i]] < 0: need[s[i]] += 1; i += 1\n",
    "                if not J or j - i <= J - I: I, J = i, j\n",
    "                need[s[i]] += 1; i += 1; missing += 1       # SPEEEEEEEED UP!\n",
    "        return s[I : J]   #有点烦  第二遍再来操作你   很烦   很乱   难受"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        left, right, count, tcounnt = 0, 0, 0, 0\n",
    "        res, queue = \"\", []\n",
    "        tdict, valid = {}, {}\n",
    "        for item in t:\n",
    "            count += 1\n",
    "            tdict[item] = 0\n",
    "            valid[item] = valid[item]+1 if item in valid else 1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in t:\n",
    "                left, right = i, i\n",
    "                break\n",
    "        print(right)\n",
    "        while right < len(s):\n",
    "            # 如果不有效right++\n",
    "            if s[right] in t:\n",
    "                tdict[s[right]] += 1\n",
    "                queue.append(right)\n",
    "                if tdict[s[right]] <= valid[s[right]]:\n",
    "                    tcounnt += 1\n",
    "            if count == tcounnt:\n",
    "                print(left,right)\n",
    "                if not res:\n",
    "                    res = s[left:right+1]\n",
    "                else:\n",
    "                    if right - left + 1 < len(res):\n",
    "                        res = s[left:right+1]\n",
    "                del queue[0]\n",
    "                tdict[s[left]] -= 1\n",
    "                if tdict[s[left]] < valid[s[left]]:\n",
    "                    tcounnt -= 1\n",
    "                if not queue:\n",
    "                    right += 1\n",
    "                    left = right\n",
    "                    continue\n",
    "                else:\n",
    "                    left = queue[0]\n",
    "                while tcounnt == count and queue:\n",
    "                    # print(\"while\",left,right)\n",
    "                    if right - left + 1 < len(res):\n",
    "                        res = s[left:right+1]\n",
    "                    del queue[0]\n",
    "                    tdict[s[left]] -= 1\n",
    "                    if tdict[s[left]] < valid[s[left]]:\n",
    "                        tcounnt -= 1\n",
    "                    if not queue:\n",
    "                        right += 1\n",
    "                        left = right\n",
    "                        continue\n",
    "                    else:\n",
    "                        left = queue[0]\n",
    "            \n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if len(s) < len(t):\n",
    "            return ''\n",
    "        if s == '' or t == '':\n",
    "            return ''\n",
    "        maps = {}\n",
    "        for i in range(len(t)):\n",
    "            maps[t[i]] = maps.get(t[i], 0) + 1\n",
    "        ##maps = collections.Counter(t)\n",
    "        counter = len(maps.keys())\n",
    "        \n",
    "        begin, end, head, length = 0, 0, 0, float('inf') # inf: 正无穷\n",
    "        while end < len(s):\n",
    "            if s[end] in maps:\n",
    "                maps[s[end]] -= 1\n",
    "                if maps[s[end]] == 0:\n",
    "                    counter -= 1                    \n",
    "            end += 1\n",
    "            \n",
    "            while counter == 0:\n",
    "                if s[begin] in maps:\n",
    "                    maps[s[begin]] += 1\n",
    "                    if maps[s[begin]] > 0:\n",
    "                        counter += 1\n",
    "                    if end - begin < length:\n",
    "                        length = end - begin\n",
    "                        head = begin\n",
    "                        \n",
    "                begin += 1\n",
    "            \n",
    "        if length == float('inf'):\n",
    "            return ''\n",
    "            \n",
    "        return s[head : head + length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def is_window_ok(self,map_s, map_t, cnt_t):\n",
    "#         for i in cnt_t:\n",
    "#             if map_s[i] < map_t[i]:\n",
    "#                 return False\n",
    "#         return True\n",
    "#     def minWindow(self, s, t):\n",
    "#         result = ''\n",
    "#         min_window_len = len(s)#init\n",
    "\n",
    "#         char_map_len = 128\n",
    "#         map_s_window = [0] * char_map_len\n",
    "#         map_t = [0] * char_map_len\n",
    "#         cnt_t = []\n",
    "#         for c in t:\n",
    "#             map_t[ord(c)] += 1\n",
    "#         for i in range(len(map_t)):\n",
    "#             if map_t[i]>0:\n",
    "#                 cnt_t.append(i)\n",
    "\n",
    "#         left = right = 0\n",
    "#         n = len(s)\n",
    "#         while right !=n:\n",
    "#             map_s_window[ord(s[right])] += 1\n",
    "\n",
    "\n",
    "#             #每次新加一个字符进来，尝试移动left，删除多余字符\n",
    "#             while left != right:\n",
    "#                 val = ord(s[left])\n",
    "#                 if (val not in cnt_t) or (map_s_window[val] > map_t[val]):#两种情况，这个字符压根不在t中，这个字符在t中，但是数量足够。\n",
    "#                     map_s_window[val] -= 1\n",
    "#                     left += 1\n",
    "#                 else:\n",
    "#                     break\n",
    "#             if self.is_window_ok(map_s_window,map_t,cnt_t):\n",
    "#                 if right - left + 1 <= min_window_len:#要包含等于，因为至少要更新一次，s='a',t='a'\n",
    "#                     min_window_len = right - left + 1\n",
    "#                     result = s[left:right+1]\n",
    "\n",
    "#             #iterate\n",
    "#             right += 1\n",
    "#         return result\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        MAX_INT = 2147483647\n",
    "        start = end = 0\n",
    "        char_need = defaultdict(int)   \n",
    "        count_need = len(t)             # count of chars not in current window but in t\n",
    "        min_length = MAX_INT\n",
    "        min_start = 0\n",
    "        for i in t:\n",
    "            # current window needs all char in t\n",
    "            char_need[i] += 1           \n",
    "        while end < len(s):\n",
    "            if char_need[s[end]] > 0:\n",
    "                count_need -= 1\n",
    "            # current window contains s[end] now, so does not need it any more\n",
    "            char_need[s[end]] -= 1      \n",
    "            end += 1\n",
    "            while count_need == 0:\n",
    "                if min_length > end - start:\n",
    "                    min_length = end - start\n",
    "                    min_start = start\n",
    "                # current window does not contain s[start] any more\n",
    "                char_need[s[start]] += 1    \n",
    "                # when some count in char_need is positive, it means there is char in t but not current window\n",
    "                if char_need[s[start]] > 0: \n",
    "                    count_need += 1\n",
    "                start += 1\n",
    "        return \"\" if min_length == MAX_INT else s[min_start:min_start + min_length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def is_window_ok(self,map_s, map_t, cnt_t):\n",
    "        for i in cnt_t:\n",
    "            if map_s[i] < map_t[i]:\n",
    "                return False\n",
    "        return True\n",
    "    def minWindow(self, s, t):\n",
    "        result = ''\n",
    "        min_window_len = len(s)#init\n",
    "\n",
    "        char_map_len = 128\n",
    "        map_s_window = [0] * char_map_len\n",
    "        map_t = [0] * char_map_len\n",
    "        cnt_t = []\n",
    "        for c in t:\n",
    "            map_t[ord(c)] += 1\n",
    "        for i in range(len(map_t)):\n",
    "            if map_t[i]>0:\n",
    "                cnt_t.append(i)\n",
    "\n",
    "        left = right = 0\n",
    "        n = len(s)\n",
    "        while right !=n:\n",
    "            map_s_window[ord(s[right])] += 1\n",
    "\n",
    "            #每次新加一个字符进来，尝试移动left，删除多余字符\n",
    "            while left != right:\n",
    "                val = ord(s[left])\n",
    "\n",
    "                # if (val not in cnt_t) or (map_s_window[val] > map_t[val]):#两种情况，这个字符压根不在t中，这个字符在t中，但是数量足够。\n",
    "                #     map_s_window[val] -= 1\n",
    "                #     left += 1\n",
    "                # else:\n",
    "                #     break\n",
    "                #这个方法的not in太费时间了？尝试优化！！！   \n",
    "                if map_t[val] == 0:\n",
    "                    left += 1\n",
    "                elif map_s_window[val] > map_t[val]:\n",
    "                    map_s_window[val] -= 1\n",
    "                    left+=1\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "                    \n",
    "            if self.is_window_ok(map_s_window,map_t,cnt_t):\n",
    "                #if right - left + 1 <= min_window_len:##要包含等于，因为至少要更新一次，s='a',t='a'\n",
    "                if result == '' or right - left + 1 <= min_window_len:#这两种方法都能解决问题\n",
    "                    min_window_len = right - left + 1\n",
    "                    result = s[left:right+1]\n",
    "            right += 1\n",
    "        return result\n",
    "\n",
    "\n",
    "# from collections import defaultdict\n",
    "# class Solution:\n",
    "#     def minWindow(self, s, t):\n",
    "#         \"\"\"\n",
    "#         :type s: str\n",
    "#         :type t: str\n",
    "#         :rtype: str\n",
    "#         \"\"\"\n",
    "#         MAX_INT = 2147483647\n",
    "#         start = end = 0\n",
    "#         char_need = defaultdict(int)   \n",
    "#         count_need = len(t)             # count of chars not in current window but in t\n",
    "#         min_length = MAX_INT\n",
    "#         min_start = 0\n",
    "#         for i in t:\n",
    "#             # current window needs all char in t\n",
    "#             char_need[i] += 1           \n",
    "#         while end < len(s):\n",
    "#             if char_need[s[end]] > 0:\n",
    "#                 count_need -= 1\n",
    "#             # current window contains s[end] now, so does not need it any more\n",
    "#             char_need[s[end]] -= 1      \n",
    "#             end += 1\n",
    "#             while count_need == 0:\n",
    "#                 if min_length > end - start:\n",
    "#                     min_length = end - start\n",
    "#                     min_start = start\n",
    "#                 # current window does not contain s[start] any more\n",
    "#                 char_need[s[start]] += 1    \n",
    "#                 # when some count in char_need is positive, it means there is char in t but not current window\n",
    "#                 if char_need[s[start]] > 0: \n",
    "#                     count_need += 1\n",
    "#                 start += 1\n",
    "#         return \"\" if min_length == MAX_INT else s[min_start:min_start + min_length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        \"\"\"The current window is s[i:j] and the result window is s[I:J]. In need[c] I store how many times I need character c (can be negative) and missing tells how many characters are still missing. In the loop, first add the new character to the window. Then, if nothing is missing, remove as much as possible from the window start and then update the result.\"\"\"\n",
    "        need, missing = collections.Counter(t), len(t)\n",
    "        print(need)\n",
    "        i = I = J = 0\n",
    "        for j, c in enumerate(s, 1):\n",
    "            print(j,c)\n",
    "            missing -= need[c] > 0\n",
    "            need[c] -= 1\n",
    "            # j之前的字符串包含所有t\n",
    "            if not missing:\n",
    "                # 找到第一个need[s[i]]==0的字符的位置\n",
    "                while i < j and need[s[i]] < 0:\n",
    "                    need[s[i]] += 1\n",
    "                    i += 1\n",
    "                # update the result\n",
    "                if not J or j - i <= J - I:\n",
    "                    I, J = i, j\n",
    "        print(s[I:J])\n",
    "        return s[I:J]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        left, right = 0, 0\n",
    "        # valid count 表示一共需要的有效的总数\n",
    "        # now valid count 目前找到的有效的总数\n",
    "        vc, nvc = 0, 0\n",
    "        # res 用于存储结果，存储字符串的开始和结尾\n",
    "        res = [-1, -1]\n",
    "        # 用于存储t中的字母出现在s中的每一个位置\n",
    "        indexs = []\n",
    "        # vd ：valid dict 用于记录目标字符串中每个字符需要出现的次数\n",
    "        # nvd: now valid dict 目前找的的有效字符的个数\n",
    "        vd, nvd = {}, {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in t:\n",
    "                indexs.append(i)\n",
    "        if not indexs:\n",
    "            return \"\"\n",
    "        for item in t:\n",
    "            vc += 1\n",
    "            nvd[item] = 0\n",
    "            vd[item] = vd[item]+1 if item in vd else 1\n",
    "        for right in range(len(indexs)):\n",
    "            nvd[s[indexs[right]]] += 1\n",
    "            if nvd[s[indexs[right]]] <= vd[s[indexs[right]]]:\n",
    "                nvc += 1\n",
    "            while self.check(left, right, vc, nvc):\n",
    "                self.put(res, indexs, left, right)\n",
    "                nvd[s[indexs[left]]] -= 1\n",
    "                if nvd[s[indexs[left]]] < vd[s[indexs[left]]]:\n",
    "                    nvc -= 1\n",
    "                left += 1\n",
    "        return '' if res[0] == -1 else s[res[0]:res[1]+1]\n",
    "\n",
    "    def check(self, left, right, vc, nvc):\n",
    "        if left > right:\n",
    "            return False\n",
    "        elif vc == nvc:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def put(self, res, indexs, left, right):\n",
    "        subtraction = res[1]-res[0]\n",
    "        if subtraction == 0 or subtraction > indexs[right]-indexs[left]:\n",
    "            res[0], res[1] = indexs[left], indexs[right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "from collections import *\n",
    "import heapq\n",
    "class Solution:\n",
    "\tdef minWindow(self, s, t):\n",
    "\t\tdict1=defaultdict(list)\n",
    "\t\t#滑动窗口模型\n",
    "\t\tc1=Counter(t)\n",
    "\t\tc2=c1.copy()\n",
    "\t\tc3=Counter()\n",
    "\t\tfor i in range(len(s)):\n",
    "\t\t\tif s[i] in c2:\n",
    "\t\t\t\tif c2[s[i]]>=1:c2[s[i]]-=1\n",
    "\t\t\t\tdict1[s[i]].append(i)\n",
    "\t\t\t\tc3[s[i]]+=1\n",
    "\t\t\tif any(c2.values())==False:break\n",
    "\t\t#print(c2.values())\n",
    "\t\tif any(c2.values())==True:return \"\"\n",
    "\t\t#保存index，对应的元素，对应的在字符的位值\n",
    "\t\theap1=[(dict1[x][0],x,0) for x in dict1]\n",
    "\t\theapq.heapify(heap1)\n",
    "\t\twhile c3[heap1[0][1]]>c1[heap1[0][1]]:\n",
    "\t\t\tuu=heap1[0]\n",
    "\t\t\theapq.heappushpop(heap1,(dict1[uu[1]][uu[2]+1],uu[1],uu[2]+1))\n",
    "\t\t\tc3[uu[1]]-=1\n",
    "\t\tp=heap1[0][0]\n",
    "\t\tq=i\n",
    "\t\tlength=q-p+1\n",
    "\t\t#print(p,q,heap1,c3)\n",
    "\t\tres=[p,q]\n",
    "\t\tfor j in range(q+1,len(s)):\n",
    "\t\t\t#print(j,s[j],c3,res,heap1)\n",
    "\t\t\tif s[j] in c1:\n",
    "\t\t\t\tdict1[s[j]].append(j)\n",
    "\t\t\t\tq=j\n",
    "\t\t\t\tc3[s[j]]+=1\n",
    "\t\t\t\tuu=heap1[0]\n",
    "\t\t\t\t#if j==12:print(s[res[0]:res[1]+1],p,q,heap1)\n",
    "\t\t\t\tif s[j]==uu[1]:\n",
    "\t\t\t\t\theapq.heappushpop(heap1,(dict1[uu[1]][uu[2]+1],uu[1],uu[2]+1))\n",
    "\t\t\t\t\tc3[s[j]]-=1\n",
    "\t\t\t\t\t#if j==10:print(heap1[0][1],c3[heap1[0][1]],c1[heap1[0][1]])\n",
    "\t\t\t\t\twhile c3[heap1[0][1]]>c1[heap1[0][1]]:\n",
    "\t\t\t\t\t\tuu=heap1[0]\n",
    "\t\t\t\t\t\t#print(heap1,(dict1[uu[1]][uu[2]+1],uu[1],uu[2]+1))\n",
    "\t\t\t\t\t\theapq.heappushpop(heap1,(dict1[uu[1]][uu[2]+1],uu[1],uu[2]+1))\n",
    "\t\t\t\t\t\tc3[uu[1]]-=1\n",
    "\t\t\t\t\tp=heap1[0][0]\n",
    "\t\t\t\t\t#if j==10:print(p,q)\n",
    "\t\t\t\t\tif q-p+1<length:\n",
    "\t\t\t\t\t\tlength=q-p+1\n",
    "\t\t\t\t\t\tres=[p,q]\n",
    "\t\treturn s[res[0]:res[1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        indexMap={}#记录上一次出现的位置\n",
    "        countMap={}\n",
    "        queueHeadMap={}\n",
    "        countC=0\n",
    "\n",
    "        for c in t:\n",
    "            if c not in indexMap.keys():\n",
    "                indexMap[c]=[]\n",
    "                countMap[c]=1\n",
    "                queueHeadMap[c]=-1\n",
    "            else:\n",
    "                countMap[c]=countMap[c]+1\n",
    "\n",
    "        for c,count in countMap.items():\n",
    "            countC+=count\n",
    "\n",
    "        start=0\n",
    "        end=0\n",
    "        length=-1\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            c=s[i]\n",
    "            if c not in indexMap.keys():\n",
    "                continue\n",
    "            indexMap[c].append(i)\n",
    "            if countMap[c]>0:\n",
    "                countMap[c]=countMap[c]-1\n",
    "                countC-=1\n",
    "            if countMap[c]==0:\n",
    "                queueHeadMap[c]=queueHeadMap[c]+1\n",
    "\n",
    "            if countC==0:\n",
    "                minIdx=i\n",
    "                for c, head in queueHeadMap.items():\n",
    "                    if indexMap[c][head]<minIdx:\n",
    "                        minIdx=indexMap[c][head]\n",
    "                l=i-minIdx+1\n",
    "                if length<0 or length>l:\n",
    "                    length=l\n",
    "                    start=minIdx\n",
    "                    end=i\n",
    "\n",
    "        if length<0:\n",
    "            return \"\"\n",
    "        return s[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "# class Solution:\n",
    "#     def minWindow(self, s: 'str', t: 'str') -> 'str':\n",
    "#         i =0; j = len(t)-1\n",
    "#         step = float(\"inf\")\n",
    "#         res = \"\"\n",
    "#         dic = Counter(t)\n",
    "#         while j <len(s):\n",
    "#             # print(s[i:j+1])\n",
    "#             if self.helper(s[i:j+1],dic):\n",
    "#                 # print(s[i:j+1])\n",
    "#                 if j-i+1<step:\n",
    "#                     step = j-i+1\n",
    "#                     res = s[i:j+1]\n",
    "#                 i += 1\n",
    "#             else:\n",
    "#                 j += 1\n",
    "#         return res\n",
    "#     def helper(self,sc,dic):\n",
    "#         temp = Counter(sc)\n",
    "#         for e in dic:\n",
    "#             if dic[e] > temp[e]:\n",
    "#                 return False\n",
    "#         return True\n",
    "class Solution(object):\n",
    "    def minWindow(self, s, t):\n",
    "        from collections import defaultdict\n",
    "        i = j = 0\n",
    "        count = len(t)\n",
    "        step = float(\"inf\")\n",
    "        res = \"\"\n",
    "        dic = defaultdict(int)\n",
    "        for e in t:\n",
    "            dic[e] += 1\n",
    "        while j < len(s):\n",
    "            if dic[s[j]] > 0:\n",
    "                count -= 1\n",
    "            dic[s[j]] -= 1\n",
    "            \n",
    "            while count == 0:\n",
    "                if step > j-i+1:\n",
    "                    step = j-i+1\n",
    "                    res = s[i:j+1]\n",
    "                if dic[s[i]] == 0:\n",
    "                    count += 1\n",
    "                dic[s[i]] += 1\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return res\n",
    "    \n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: 'str', t: 'str') -> 'str':\n",
    "        dicT = collections.Counter(t)\n",
    "        dicS = {}\n",
    "        rec = set()\n",
    "        j = 0\n",
    "        res = float('inf')\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in dicS:\n",
    "                dicS[c] = 1\n",
    "            else:\n",
    "                dicS[c] += 1\n",
    "            if c in dicT and dicT[c] <= dicS[c]:\n",
    "                rec.add(c)\n",
    "                while len(rec) == len(dicT):\n",
    "                    dicS[s[j]] -= 1\n",
    "                    if s[j] in dicT and dicT[s[j]] > dicS[s[j]]:\n",
    "                        rec.remove(s[j])\n",
    "                        if res > i-j+1:\n",
    "                            start = j\n",
    "                            end = i\n",
    "                            res = i-j+1\n",
    "                    j += 1\n",
    "        if res == float('inf'):\n",
    "            return \"\"\n",
    "        return s[start:end+1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    #https://leetcode.com/problems/minimum-window-substring/discuss/26804/12-lines-Python\n",
    "    def minWindow(self, s, t):\n",
    "        need = collections.Counter(t)\n",
    "        i, miss = 0, len(t)\n",
    "        start, end = 0, 0\n",
    "        \n",
    "        for j in range(len(s)):\n",
    "            if need[s[j]] > 0:\n",
    "                miss -= 1\n",
    "            need[s[j]] -= 1\n",
    "\n",
    "            if miss == 0:\n",
    "                while i <= j and need[s[i]] < 0:\n",
    "                    need[s[i]] += 1\n",
    "                    i += 1\n",
    "                need[s[i]] += 1\n",
    "                miss += 1\n",
    "                if end == 0 or (j-i) < (end-start):\n",
    "                    start, end = i, j+1\n",
    "                i += 1\n",
    "\n",
    "        return s[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if not s or not t:\n",
    "            return ''\n",
    "        from collections import defaultdict\n",
    "        tc = defaultdict(int)\n",
    "        for ts in t:\n",
    "            tc[ts] += 1\n",
    "        sl,tl = len(s),len(t)\n",
    "        left, l, r =0, 0, sl\n",
    "        for right,c in enumerate(s):\n",
    "            if tc[c]>0:\n",
    "                tl -= 1\n",
    "            tc[c] -= 1\n",
    "            if not tl:\n",
    "                while tc[s[left]]<0:\n",
    "                    tc[s[left]]+=1 \n",
    "                    left += 1                                         \n",
    "                if (r-l) > (right - left):\n",
    "                    l,r = left, right\n",
    "                tc[s[left]] += 1  \n",
    "                left += 1\n",
    "                tl += 1              \n",
    "        return s[l:r+1] if r<sl else ''\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        if not s or not t:\n",
    "            return ''\n",
    "        left, right = 0, 0\n",
    "        window = collections.defaultdict(int)\n",
    "        pattern = collections.Counter(t)\n",
    "        # 统计t的种类\n",
    "        count = len(pattern)\n",
    "        formed = 0\n",
    "        res = (float('inf'), 0, 0)\n",
    "        while right < len(s):\n",
    "            ch = s[right]\n",
    "            window[ch] += 1\n",
    "            if ch in pattern and window[ch] == pattern[ch]:\n",
    "                formed += 1\n",
    "            # 进入滑动窗口\n",
    "            while left <= right and formed == count:\n",
    "                ch = s[left]\n",
    "                if right - left + 1 < res[0]:\n",
    "                    res = (right - left + 1, left, right)\n",
    "                window[ch] -= 1\n",
    "                if ch in pattern and window[ch] < pattern[ch]:\n",
    "                    formed -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return \"\" if res[0] == float('inf') else s[res[1]: res[-1] + 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "#     def minWindow(self, s: str, t: str) -> str:\n",
    "#         if len(s) < len(t) or not t:\n",
    "#             return ''\n",
    "#         t_dic = defaultdict(lambda: 0)\n",
    "#         win_dic = defaultdict(lambda: 0)\n",
    "#         for i in t:\n",
    "#             t_dic[i] += 1\n",
    "#         min_len = len(s) + 1\n",
    "#         sub = [0, 0]\n",
    "#         left, right = 0, 0\n",
    "#         distance = 0\n",
    "#         while right < len(s):\n",
    "#             if win_dic[s[right]] < t_dic[s[right]]:\n",
    "#                 distance += 1\n",
    "#             win_dic[s[right]] += 1\n",
    "#             right += 1\n",
    "            \n",
    "#             while distance == len(t):\n",
    "#                 if win_dic[s[left]] > t_dic[s[left]]:\n",
    "#                     win_dic[s[left]] -= 1\n",
    "#                     left += 1\n",
    "#                 else:\n",
    "#                     if right - left < min_len:\n",
    "#                         min_len = right - left\n",
    "#                         sub = [left, right]\n",
    "#                     break\n",
    "                    \n",
    "#         if min_len == len(s) + 1:\n",
    "#             return ''\n",
    "#         return s[sub[0]: sub[1]]\n",
    "    def minWindow(self, s, t):\n",
    "        need, missing = collections.Counter(t), len(t)\n",
    "        i = I = J = 0\n",
    "        for j, c in enumerate(s, 1):\n",
    "            missing -= need[c] > 0\n",
    "            need[c] -= 1\n",
    "            if not missing:\n",
    "                while i < j and need[s[i]] < 0:\n",
    "                    need[s[i]] += 1\n",
    "                    i += 1\n",
    "                if not J or j - i <= J - I:\n",
    "                    I, J = i, j\n",
    "        return s[I:J]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for ch in t:\n",
    "            dic[ch]+=1\n",
    "        left = 0\n",
    "        count = len(t)\n",
    "        res = (0,float('inf'))\n",
    "        for right,ch in enumerate(s):\n",
    "            if dic[ch]>0:\n",
    "                count-=1\n",
    "            dic[ch]-=1\n",
    "            if count==0:\n",
    "                while True:\n",
    "                    temp = s[left]\n",
    "                    if dic[temp]==0:\n",
    "                        break\n",
    "                    dic[temp]+=1\n",
    "                    left+=1\n",
    "                if right-left<res[1]-res[0]:\n",
    "                    res = (left,right)\n",
    "                count+=1\n",
    "                dic[s[left]]+=1\n",
    "                left+=1\n",
    "        if res[1]>len(s):\n",
    "            return ''\n",
    "        return s[res[0]:res[1]+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        def ord_c(c):\n",
    "            return ord(c)-ord(\"a\")\n",
    "\n",
    "        max_len=128\n",
    "        chars=[0]*max_len       #每个字符缺少的数量\n",
    "        flag=[False]*max_len    #每个字符是否在T中存在\n",
    "\n",
    "        # 统计T中的字符情况\n",
    "\n",
    "        for c in t:\n",
    "            flag[ord_c(c)]=True\n",
    "            chars[ord_c(c)]+=1\n",
    "\n",
    "        cnt=0   #表示窗口中包含t的数量\n",
    "        l=0     #窗口的左指针\n",
    "        min_l=0   #当前最短序列的左指针\n",
    "        min_size=len(s)+1       #当前最短序列的长度\n",
    "\n",
    "        for r,c in enumerate(s):\n",
    "            # 如果这个字符不在T中，右指针继续右移\n",
    "            if not flag[ord_c(c)]:\n",
    "                continue\n",
    "\n",
    "            # 需要这个字符的数量--\n",
    "            chars[ord_c(c)]-=1\n",
    "            if chars[ord_c(c)]>=0:\n",
    "                cnt+=1\n",
    "\n",
    "            # 如果当前窗口已经包括T中的所有字符\n",
    "            # 尝试将左指针l右移，找到更短的字符串\n",
    "            while cnt==len(t):\n",
    "                if r-l+1<min_size:\n",
    "                    min_l=l\n",
    "                    min_size=r-l+1\n",
    "\n",
    "                if flag[ord_c(s[l])]:\n",
    "                    chars[ord_c(s[l])]+=1\n",
    "                    if chars[ord_c(s[l])]>0:\n",
    "                        cnt-=1\n",
    "\n",
    "                l+=1\n",
    "\n",
    "        if min_size>len(s):\n",
    "            return \"\"\n",
    "        else:\n",
    "            return s[min_l:min_l+min_size]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        left = right = 0\n",
    "        needer = {}\n",
    "        for c in t:\n",
    "            needer[c] = needer.get(c,0) + 1\n",
    "        window = {}\n",
    "        match = 0\n",
    "        res = ''\n",
    "        N = len(s)\n",
    "        min_val = N \n",
    "        match_N = len(needer)\n",
    "        while right < N:\n",
    "            if s[right] in needer:\n",
    "                window[s[right]] = window.get(s[right], 0) + 1\n",
    "\n",
    "                if window[s[right]] == needer[s[right]]:\n",
    "                    match += 1\n",
    "            while match == match_N:\n",
    "                this_time_val = right - left\n",
    "                if min_val > this_time_val:\n",
    "                    res = s[left: right+1]\n",
    "                    min_val = this_time_val\n",
    "                \n",
    "                if s[left] in needer:\n",
    "                    window[s[left]] -= 1\n",
    "                    if window[s[left]] < needer[s[left]]:\n",
    "                        match -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        count = len(t)\n",
    "        chars = dict()\n",
    "        deque = collections.deque()\n",
    "        left, right = 0, 0\n",
    "\n",
    "        for i in range(len(t)):\n",
    "            if t[i] in chars:\n",
    "                chars[t[i]] += 1\n",
    "            else:\n",
    "                chars[t[i]] = 1\n",
    "        \n",
    "        while right < len(s) and count > 0:\n",
    "            if s[right] in chars:\n",
    "                deque.append(right)\n",
    "                chars[s[right]] -= 1\n",
    "                if chars[s[right]] >= 0:\n",
    "                    count -= 1\n",
    "            right += 1\n",
    "        \n",
    "        if count > 0:\n",
    "            return \"\"\n",
    "\n",
    "        left = deque.popleft()\n",
    "        while chars[s[left]] < 0:\n",
    "            chars[s[left]] += 1\n",
    "            left = deque.popleft()\n",
    "        min_len = right - left\n",
    "        res = s[left : right]\n",
    "\n",
    "        while right < len(s):\n",
    "            if s[right] == s[left]:\n",
    "                left = deque.popleft()\n",
    "                while chars[s[left]] < 0:\n",
    "                    chars[s[left]] += 1\n",
    "                    left = deque.popleft()\n",
    "                if right - left + 1 < min_len:\n",
    "                    min_len = right - left + 1\n",
    "                    res = s[left : right + 1]\n",
    "                deque.append(right)\n",
    "            elif s[right] in chars:\n",
    "                deque.append(right)\n",
    "                chars[s[right]] -= 1\n",
    "            right += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        missing = len(t)\n",
    "        if not s or not missing or len(s) < missing:\n",
    "            return \"\"\n",
    "\n",
    "        start = end = i = 0\n",
    "        need = collections.Counter(t)\n",
    "        for j, char in enumerate(s, 1):\n",
    "            if need[char] > 0:\n",
    "                missing -= 1\n",
    "            need[char] -= 1\n",
    "            print(missing)\n",
    "            if missing == 0:\n",
    "                while i < j and need[s[i]] < 0:\n",
    "                    need[s[i]] += 1\n",
    "                    i += 1\n",
    "                if not end or j - i < end - start:\n",
    "                    start, end = i, j\n",
    "        return s[start:end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def get_t_count(t):\n",
    "        t_count = dict()\n",
    "        for i, val in enumerate(t):\n",
    "            t_count[val] = t_count.get(val, 0) + 1\n",
    "        return t_count\n",
    "\n",
    "    def judge(self, s_count, t_count):\n",
    "        if len(s_count) < len(t_count):\n",
    "            return False\n",
    "        for letter, count in t_count.items():\n",
    "            if s_count.get(letter, 0) < count:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        len_s = len(s)\n",
    "        len_t = len(t)\n",
    "        if len_s < len_t:\n",
    "            return \"\"\n",
    "        t = list(t)\n",
    "        s = list(s)\n",
    "        t_count = self.get_t_count(t)\n",
    "\n",
    "        res = \" \" * (len_s + 1)\n",
    "        s_count = dict()\n",
    "        i = 0\n",
    "        for j, val in enumerate(s):  # ADOBECODEBANC\n",
    "            s_count[val] = s_count.get(val, 0) + 1\n",
    "            while self.judge(s_count, t_count):\n",
    "                if len(s[i:j+1]) < len(res):\n",
    "                    res = s[i:j+1]\n",
    "                s_count[s[i]] = s_count.get(s[i]) - 1\n",
    "                i += 1\n",
    "        return \"\".join(res) if len(res) < len_s + 1 else \"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        need = defaultdict(int)\n",
    "        # 初始化need\n",
    "        for c in t:\n",
    "            need[c] += 1\n",
    "        needcnt = len(t)  # 初始化needcnt\n",
    "        i = 0\n",
    "        res = (0, float('inf'))\n",
    "        # 枚举s\n",
    "        for j, c in enumerate(s):\n",
    "            if need[c] > 0:\n",
    "                needcnt -= 1\n",
    "            need[c] -= 1\n",
    "            if needcnt == 0:  # 窗口元素符合条件\n",
    "                while True:\n",
    "                    c = s[i]\n",
    "                    if need[c] == 0:  # 必须包含的元素\n",
    "                        # print(need)\n",
    "                        break\n",
    "                    need[c] += 1  # 排除不必要的元素\n",
    "                    i += 1\n",
    "                if j - i < res[1] - res[0]:\n",
    "                    res = (i, j)  # 保存窗口的最小长度\n",
    "                    # print(res)\n",
    "                need[s[i]] += 1  # i增加一个位置，寻找新窗口\n",
    "                needcnt += 1\n",
    "                i += 1\n",
    "        return '' if len(s) < res[1] else s[res[0]:res[1] + 1]  # res[1]没有被更新过，即表示没有符合的子串。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minWindow(self, s: str, t: str) -> str:\n",
    "#     # s = input()\n",
    "#     # t = input()\n",
    "#         def minstr(s,t,list2):\n",
    "#             a =t\n",
    "#             list1 = []\n",
    "#             flag = True\n",
    "#             if len(s) >= len(t):\n",
    "#                 for i in range(len(s)):\n",
    "#                     if s[i] in a:\n",
    "#                         a = a.replace(s[i], \"\",1)\n",
    "#                         list1.append(i)\n",
    "#                     if s[i] in t:\n",
    "#                         flag = False\n",
    "#                     if a == \"\" :\n",
    "#                         list2.append(s[list1[0]:list1[-1] + 1])\n",
    "#                         if i != len(s) - 1 or flag == False:\n",
    "#                             a = t\n",
    "#                             s = s[list1[0] + 1:]\n",
    "#                             minstr(s, a, list2)\n",
    "#                             return list2\n",
    "\n",
    "\n",
    "#             else:\n",
    "#                 return list2\n",
    "\n",
    "#         list2 = []\n",
    "#         minstr(s,t,list2)\n",
    "#         if len(list2) == 0:\n",
    "#             return(\"\")\n",
    "#         else:\n",
    "#             min = list2[0]\n",
    "#             for i in range(len(list2)):\n",
    "#                 if len(list2[i]) <= len(min):\n",
    "#                     min = list2[i]\n",
    "#             min = min\n",
    "#             return(min )\n",
    "# class Solution:\n",
    "#     def minWindow(self, s: str, t: str) -> str:\n",
    "#         need = collections.defaultdict(int)#建立目标字符字典\n",
    "#         for ch in t:\n",
    "#             need[ch] += 1#统计t中item\n",
    "        \n",
    "#         left, min_len = 0, len(s)#初始化为长度更合理\n",
    "#         sstart, send = -1, -1\n",
    "\n",
    "#         for right, item in enumerate(s):#right是下标位置，item是char\n",
    "#             if item in need.keys():\n",
    "#                 need[item] -= 1\n",
    "                \n",
    "#             while self.isAllSatisfied(need):#全部item计数小于等于0循环\n",
    "#                 min_len = min(min_len, right - left +1)\n",
    "#                 if sstart == send == -1 or send-sstart >= right - left:\n",
    "#                     sstart, send = left, right#如果 默认初始位置，或区域变小，则更新\n",
    "#                 if s[left] in need.keys():\n",
    "#                     need[s[left]] +=1#左侧字符出现在need，则更新字典，若有小于0计数结果，依然成立\n",
    "#                 left +=1#左侧右移\n",
    "#         return s[sstart:send+1]\n",
    "\n",
    "#     def isAllSatisfied(self, dict_):\n",
    "#         for k,v in dict_.items():\n",
    "#             if v>0:\n",
    "#                 return False\n",
    "#         return True\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        dic = collections.Counter(t)\n",
    "        left = 0\n",
    "        temp = float('inf')\n",
    "        res = \"\"\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in dic:\n",
    "                dic[s[right]] -= 1\n",
    "\n",
    "            while max(dic.values()) == 0:\n",
    "                if temp > right-left+1:\n",
    "                    temp =  right-left+1\n",
    "                    res = s[left:right+1]\n",
    "                if s[left] in dic:\n",
    "                    dic[s[left]] += 1\n",
    "                left += 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        need,windows = defaultdict(int), defaultdict(int)\n",
    "        for c in t:\n",
    "            need[c] += 1\n",
    "        \n",
    "        valid,left,right = 0,0,0\n",
    "        length = float('inf')\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            if c in need:\n",
    "                windows[c] += 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            while valid == len(need):\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "                \n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "\n",
    "        return \"\" if length == float('inf') else s[start:start + length]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        # 初始化\n",
    "        need, windows = defaultdict(int), defaultdict(int)\n",
    "        for i in t:\n",
    "            need[i]+=1\n",
    "        \n",
    "        left,right = 0, 0\n",
    "        valid = 0\n",
    "        start, str_len = 0, len(s) +1\n",
    "\n",
    "        while right < len(s):\n",
    "            # 扩大字符串 直至包含所有 t\n",
    "            c = s[right]\n",
    "            right +=1\n",
    "            if c in need:\n",
    "                windows[c] +=1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid +=1\n",
    "            \n",
    "            # 收缩字符串， 更新最小长度\n",
    "            while valid == len(need):\n",
    "                if right - left < str_len:\n",
    "                    str_len = right - left\n",
    "                    start = left\n",
    "                # 移除\n",
    "                c = s[left]\n",
    "                left +=1\n",
    "                if c in need:\n",
    "                    if windows[c] == need[c]:\n",
    "                        valid -=1\n",
    "                    windows[c]-=1\n",
    "        return '' if str_len > len(s) else s[start:start+str_len]                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        n = len(t)\n",
    "        cnt = defaultdict(int)\n",
    "        for ch in t:\n",
    "            cnt[ch] += 1\n",
    "        letter_cnt = len(t)\n",
    "        i = 0\n",
    "        res = (0,10e10)\n",
    "        for j, ch in enumerate(s):\n",
    "            if cnt[ch] > 0:\n",
    "                letter_cnt -= 1\n",
    "            cnt[ch] -= 1\n",
    "            if letter_cnt == 0:\n",
    "                while True:\n",
    "                    if cnt[s[i]] == 0:\n",
    "                        break\n",
    "                    cnt[s[i]] += 1\n",
    "                    i += 1\n",
    "                if j - i < res[1] - res[0]:\n",
    "                    res = (i, j)\n",
    "                cnt[s[i]] += 1\n",
    "                letter_cnt += 1\n",
    "                i += 1\n",
    "        if res[1] == 10e10:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return s[res[0]:res[1] + 1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        req_dict={}\n",
    "        had_dict={}\n",
    "        for char in t:\n",
    "            had_dict[char]=0\n",
    "            if char in req_dict:\n",
    "                req_dict[char]+=1\n",
    "            else:\n",
    "                req_dict[char]=1\n",
    "        left , right = 0,-1\n",
    "        char_vacency = len(t)\n",
    "        min_len = len(s)+1\n",
    "        shortest_str = ''\n",
    "        while left<len(s):\n",
    "            if char_vacency>0 and s[left] in req_dict: # move right point \n",
    "                right+=1\n",
    "                if right==len(s):break\n",
    "                right_char = s[right]\n",
    "                if right_char in had_dict:\n",
    "                    had_dict[right_char]+=1\n",
    "                    if had_dict[right_char]<=req_dict[right_char]:\n",
    "                        char_vacency-=1\n",
    "                        if char_vacency==0 and min_len>right-left+1:\n",
    "                            min_len = right-left+1\n",
    "                            shortest_str = s[left:right+1]\n",
    "                print('right',right_char,char_vacency)\n",
    "            else:\n",
    "                left_char = s[left]\n",
    "                if left_char not in req_dict:\n",
    "                    pass\n",
    "                else:\n",
    "                    had_dict[left_char]-=1\n",
    "                    if had_dict[left_char]>=req_dict[left_char]:\n",
    "                        pass\n",
    "                    else:\n",
    "                        char_vacency+=1\n",
    "\n",
    "                left+=1\n",
    "                if char_vacency==0 and min_len>right-left+1:\n",
    "                    min_len = right-left+1\n",
    "                    shortest_str = s[left:right+1]\n",
    "                print('left',left_char,char_vacency)\n",
    "\n",
    "\n",
    "        return shortest_str\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        # 左右指针位置\n",
    "        left, right = 0, 0\n",
    "        # 记载有效字符的数量\n",
    "        valid = 0\n",
    "        # 记载目标字符串     \n",
    "        need = Counter(t)\n",
    "        # 窗口\n",
    "        window = need.copy()\n",
    "        for key, value in window.items():\n",
    "            window[key] = 0\n",
    "        # 记载匹配成功的串的位置\n",
    "        start = 0\n",
    "        # 记载当前最小覆盖子串的长度\n",
    "        l = 100001\n",
    "        end = 0\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "            # 当前字符在目标字符串里    \n",
    "            if c in need:\n",
    "                # 更新窗口相应的值\n",
    "                window[c] += 1\n",
    "                # 若窗口中该字符的数量和目标字符串中该字符的数量相等，有效值加一\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            # 满足条件时不断缩小窗口\n",
    "            while valid == len(need):\n",
    "                # 更新最小覆盖子串\n",
    "                if right - left < l:\n",
    "                    start = left\n",
    "                    end = right\n",
    "                    l = right - left\n",
    "                # 更新窗口左端的字符\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "        # if l == 100001:\n",
    "        #     return \"\"\n",
    "        # else:\n",
    "        return s[start: end]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for x in t:\n",
    "            cnt[x] -= 1\n",
    "        ret = \"\"\n",
    "        left, right = 0, 0\n",
    "        cnt[s[right]] += 1\n",
    "        while left < len(s) and right < len(s):\n",
    "            isMin = True\n",
    "            for k in cnt.keys():\n",
    "                if cnt[k] < 0:\n",
    "                    isMin = False\n",
    "                    break\n",
    "            if isMin:\n",
    "                if ret == \"\" or len(ret) > right - left + 1:\n",
    "                    ret = s[left:right+1]\n",
    "                cnt[s[left]] -= 1\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "                if right < len(s):\n",
    "                    cnt[s[right]] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        need = defaultdict(int)\n",
    "        for c in t:\n",
    "            need[c] += 1\n",
    "        needCnt = len(t)\n",
    "        start = 0\n",
    "        minLen = float('inf')\n",
    "        minStart = 0\n",
    "\n",
    "        for end, c in enumerate(s):\n",
    "            if need[c] > 0:\n",
    "                needCnt -= 1\n",
    "            need[c] -= 1\n",
    "\n",
    "            while needCnt == 0:  # 所有字符都被覆盖\n",
    "                if end - start < minLen:\n",
    "                    minLen = end - start\n",
    "                    minStart = start\n",
    "\n",
    "                need[s[start]] += 1\n",
    "                if need[s[start]] > 0:\n",
    "                    needCnt += 1\n",
    "                start += 1\n",
    "\n",
    "        return '' if minLen == float('inf') else s[minStart:minStart + minLen + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    \n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "\n",
    "        if len(s) < len(t):\n",
    "            return \"\"\n",
    "\n",
    "        res = sys.maxsize-1\n",
    "        save_dict = collections.defaultdict(int)\n",
    "        for i in range(len(t)):\n",
    "            save_dict[t[i]] += 1\n",
    "        \n",
    "        need_nums = len(t)\n",
    "        i = 0\n",
    "        begin = 0\n",
    "        end = len(s)-1\n",
    "\n",
    "        for j in range(0, len(s)):\n",
    "            if save_dict[s[j]] > 0:\n",
    "                need_nums -= 1\n",
    "            save_dict[s[j]] -= 1                \n",
    "            \n",
    "\n",
    "            if need_nums == 0:\n",
    "                while True:\n",
    "                    if save_dict[s[i]] == 0:\n",
    "                        break\n",
    "                    \n",
    "                    save_dict[s[i]] += 1\n",
    "                    i += 1\n",
    "                \n",
    "                if j - i < res:\n",
    "                    res = j - i\n",
    "                    begin = i\n",
    "                    end = j\n",
    "\n",
    "                save_dict[s[i]] += 1\n",
    "                i += 1\n",
    "                need_nums += 1\n",
    "\n",
    "        if i == 0:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return s[begin:end+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minWindow(self, s: str, t: str) -> str:\n",
    "        \n",
    "        left,right = 0,0\n",
    "        min_left,minlen = 0,float(\"inf\")\n",
    "        mapt,maps = {},{}\n",
    "        for ti in t:\n",
    "            mapt[ti] = mapt.get(ti,0)+1\n",
    "            maps[ti] = 0\n",
    "        while right < len(s):\n",
    "            if  s[right] in mapt:\n",
    "                maps[s[right]] = maps[s[right]] + 1\n",
    "            right +=1\n",
    "            while all(map(lambda x:maps[x]>=mapt[x],mapt.keys())):\n",
    "                if right - left < minlen:\n",
    "                    minlen = right - left\n",
    "                    min_left = left\n",
    "                if s[left] in maps:\n",
    "                    maps[s[left]] -= 1\n",
    "                left +=1\n",
    "        print(min_left,minlen)\n",
    "        return s[min_left:min_left+minlen] if minlen <= len(s) else \"\"\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
